import java.util.*;
//链表相加(二)

  class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }
  }

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList(ListNode head1, ListNode head2) {

        ListNode temp1=reverseList(head1);
        ListNode temp2=reverseList(head2);

        // 创建虚拟头节点
        ListNode newH = new ListNode(-1);
        ListNode tmp = newH;

        // 开始加法操作
        int carry = 0; // 记录进位
        while(temp1!=null||temp2!=null||carry!=0){
            int sum=carry;
            if(temp1!=null){
                sum+=temp1.val;
                temp1=temp1.next;
            }
            if(temp2!=null){
                sum+=temp2.val;
                temp2=temp2.next;
            }
            tmp.next=new ListNode(sum%10);
            tmp=tmp.next;
            carry=sum/10;
        }

        return  reverseList(newH.next);
    }
    public ListNode reverseList(ListNode headA) {
        ListNode cur = headA.next;
        headA.next=null;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=headA;
            headA=cur;
            cur=curNext;
        }
        return headA;
    }
}
